package com.sheng.leetcode.year2025.month10.day10;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/10/10
 * <p>
 * 3147. 从魔法师身上吸取的最大能量<p>
 * <p>
 * 在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。<p>
 * 你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。<p>
 * 换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。<p>
 * 给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。<p>
 * <p>
 * 示例 1：<p>
 * 输入： energy = [5,2,-10,-5,1], k = 3<p>
 * 输出： 3<p>
 * 解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。<p>
 * <p>
 * 示例 2：<p>
 * 输入： energy = [-2,-3,-1], k = 2<p>
 * 输出： -1<p>
 * 解释：可以从魔法师 2 开始，吸收能量 -1。<p>
 * <p>
 * 提示：<p>
 * 1 <= energy.length <= 10^5<p>
 * -1000 <= energy[i] <= 1000<p>
 * 1 <= k <= energy.length - 1<p>
 */
public class LeetCode3147 {

    @Test
    public void test() {
//        int[] energy = {5, 2, -10, -5, 1};
//        int k = 3;
        int[] energy = {-2, -3, -1};
        int k = 2;
//        int[] energy = {1, -3, 10, 7};
//        int k = 1;
//        int[] energy = {5, -10, 4, 3, 5, -9, 9, -7};
//        int k = 2;
        System.out.println(new Solution().maximumEnergy(energy, k));
    }
}

class Solution {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        // f[i] 表示从 i 开始，能吸收的最大能量
//        int[] f = new int[n];
//        Arrays.fill(f, Integer.MIN_VALUE);
//        for (int i = n - 1; i >= n - k; i--) {
//            f[i] = energy[i];
//        }
        int ans = Integer.MIN_VALUE;
        for (int i = n - k; i < n; i++) {
            int max = 0;
            for (int j = i; j >= 0; j -= k) {
                max += energy[j];
//                f[i] = Math.max(f[i], max);
                ans = Math.max(ans, max);
            }
        }
        return ans;
//        return Arrays.stream(f).max().getAsInt();
    }
}
